#pragma once
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <array>
#include <time.h>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <functional>
#include <assert.h>
using namespace std;

// 颜色枚举
enum Colour
{
	RED,
	BLACK,
};

// 结点类
template <class T>
struct RBTreeNode
{
	RBTreeNode<T> *_left;
	RBTreeNode<T> *_right;
	RBTreeNode<T> *_parent;
	T _data;
	Colour _col;

	RBTreeNode(const T &data)
		: _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED)
	{
	}
};

// 迭代器类
template <class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node *_node;

	// 结点构造函数
	RBTreeIterator(Node *node)
		: _node(node)
	{
	}

	RBTreeIterator(const RBTreeIterator<T, T &, T *> &it)
		: _node(it._node)
	{
	}

	// 重载解引用运算符
	Ref operator*()
	{
		return _node->_data;
	}

	// 重载成员访问运算符
	Ptr operator->()
	{
		return &_node->_data;
	}

	// 关系运算符
	bool operator!=(const Self &s)
	{
		return _node != s._node;
	}

	// 自增 ++a
	// 一棵树 最小的[begin]在左下角 最大的在右下角
	// [end指向最大的后一个即null]
	// 自增自减运算符遍历从小到大
	Self &operator++()
	{
		//_node指向当前结点

		// 右不空
		if (_node->_right)
		{
			// next为右子树最左节点

			// 右子树根节点
			Node *subLeft = _node->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}
			// 更改指向 ++成功
			_node = subLeft;
		}
		// 右空: 遍历时 一个结点右空 当前结点所在子树遍历结束
		else
		{
			// 向上回溯--next特征:右为空的结点所在子树的上一代
			Node *cur = _node;
			Node *dad = cur->_parent;
			// 如果cur是父右 向上回溯
			// 不是父右 定是父左 循环结束

			// 特殊: 当遍历到最后一个结点[右下角]  一直回溯直到dad指向根时
			// 此时再回溯一次 dad为空 循环结束 _node指向空
			while (dad && cur == dad->_right)
			{
				cur = dad;
				dad = dad->_parent;
			}
			// 更改指向 ++a成功
			_node = dad;
		}

		return *this;
	}

	// a++
	Self operator++(int)
	{
		Self it(_node);
		++*this;
		return it;
	}

	// 自减
	//++从小到大 --从大到小 ++找次小 --找次大
	Self &operator--()
	{
		// 假定_node指向最后一个结点[右一定为空]
		if (_node->_left)
		{
			// 左不空 次大为左子树最右节点
			Node *subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}
			// 更改指向 ++成功
			_node = subRight;
		}
		else
		{
			// 左为空 遍历时 一个结点左空 当前结点所在子树遍历结束

			// 向上回溯--prev特征:左为空的结点所在子树的上一代
			Node *cur = _node;
			Node *dad = cur->_parent;

			// 如果cp是父左 向上回溯
			// 不是父右 定是父左 循环结束

			// 特殊:当遍历到最后一个结点[左下角]  一直回溯直到dad指向根时
			// 此时再回溯一次 dad为空 循环结束 _node指向空
			while (dad && cur == dad->_left)
			{
				cur = dad;
				dad = dad->_parent;
			}
			// 更改指向 ++成功
			_node = dad;
		}

		return *this;
	}

	Self operator--(int)
	{
		Self it(_node);
		--*this;
		return it;
	}
};

// 红黑树类
template <class K, class T, class GetKey>
class RBTree
{
	typedef RBTreeNode<T> Node;

private:
	Node *_root = nullptr;

public:
	typedef RBTreeIterator<T, T &, T *> itertaor;
	typedef RBTreeIterator<T, const T &, const T *> const_itertaor;

	///////////////  迭代器  ////////////////////////////////////

	// begin迭代器[左路最后一个结点]
	itertaor begin()
	{
		Node *cp = _root;
		// 防止传入空树
		while (cp && cp->_left)
		{
			cp = cp->_left;
		}

		return itertaor(cp);
	}

	// end迭代器[最后一个数据的下一个位置]
	itertaor end()
	{
		return itertaor(nullptr);
	}

	// const_begin迭代器
	const_itertaor begin() const
	{
		Node *cp = _root;
		while (cp && cp->_left)
		{
			cp = cp->_left;
		}

		return const_itertaor(cp);
	}

	// const_end迭代器
	const_itertaor end() const
	{
		return const_itertaor(nullptr);
	}
	///////////////  迭代器  ////////////////////////////////////

	// 查找函数
	Node *Find(const K &key)
	{
		Node *cp = _root;
		GetKey get;
		while (cp)
		{
			if (get(cp->_data) < key)
			{
				cp = cp->_right;
			}
			else if (get(cp->_data) > key)
			{
				cp = cp->_left;
			}
			else
			{
				return cp;
			}
		}

		return nullptr;
	}

	// 插入函数
	pair<itertaor, bool> Insert(const T &data)
	{
		// 根节点为空
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK; // 根节点颜色为黑

			return make_pair(itertaor(_root), true);
		}

		// 不为空 定位至合适位置
		GetKey get;
		Node *dad = nullptr;
		Node *cur = _root;
		while (cur)
		{
			if (get(cur->_data) < get(data))
			{
				dad = cur;
				cur = cur->_right;
			}
			else if (get(cur->_data) > get(data))
			{
				dad = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(itertaor(cur), false);
			}
		}

		cur = new Node(data);
		Node *tmp = cur;
		if (get(dad->_data) > get(data))
		{
			dad->_left = cur;
		}
		else
		{
			dad->_right = cur;
		}
		cur->_parent = dad;

		// 2.构建红黑树

		// cur[红]此时定位新插入位置 若父存在且为红进入while
		while (dad && dad->_col == RED)
		{
			// 之后的循环来到此处 判断dad && dad->_col == RED
			// 父为空 则cur为根 [最后控制cur变黑] 循环结束; 父为黑 无需操作
			Node *grandpa = dad->_parent;

			// 若父为红 祖父定存在且为黑
			assert(grandpa && grandpa->_col == BLACK);

			// 2.1 判断uncle位置 分类一：父为左子树
			if (dad == grandpa->_left)
			{
				// uncle为右子树
				Node *uncle = grandpa->_right;

				// 情况一、uncle存在为红 变色+回溯
				// dad-uncle变黑 grandpa变红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					dad->_col = uncle->_col = BLACK;
					grandpa->_col = RED;
					// 回溯
					cur = grandpa;
					dad = cur->_parent;
				}

				// 情况二-三：uncle不存在 或 存在且为黑
				else
				{
					if (cur == dad->_left)
					{
						// 情况二：右单旋+变色
						RotateR(grandpa);
						dad->_col = BLACK;
						grandpa->_col = RED;
					}
					else
					{
						// 情况三：左右双旋+变色
						RotateL(dad);
						RotateR(grandpa);
						cur->_col = BLACK;
						grandpa->_col = RED;
					}

					break;
				}
			}
			// 2.2 判断uncle位置 父为右子树
			else
			{
				// uncle为左子树
				Node *uncle = grandpa->_left;
				// 情况一
				if (uncle && uncle->_col == RED)
				{
					// 变色
					dad->_col = uncle->_col = BLACK;
					grandpa->_col = RED;
					// 回溯
					cur = grandpa;
					dad = cur->_parent;
				}
				else
				{
					if (cur == dad->_right)
					{
						// 情况二：左单旋+变色
						RotateL(grandpa);
						dad->_col = BLACK;
						grandpa->_col = RED;
					}
					else
					{
						// 情况三：右左单旋+变色
						RotateR(dad);
						RotateL(grandpa);
						cur->_col = BLACK;
						grandpa->_col = RED;
					}

					break;
				}
			}
		}

		// 父不存在的情况：即该树是空树 插入的结点就是根 在该函数调用初就判断了直接把该节点变为黑即可
		// cur的父为黑 则不用操作
		_root->_col = BLACK;

		return make_pair(itertaor(tmp), true);
	}

	// 判断是否是红黑树
	bool IsRBTree()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点颜色错误!" << endl;
			return false;
		}

		// 事先计算出某一条路径黑色结点数量
		// 后续每一条路径都应和certain相等 不想等报错
		int certain = 0;
		Node *cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++certain;
			cur = cur->_left;
		}

		return PrevJudge(_root, 0, certain);
	}

	// 高度接口
	int Height()
	{
		return _Height(_root);
	}

	// 析构函数
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

private:
	// 后序遍历销毁红黑树
	void _Destroy(Node *root)
	{
		if (root == nullptr)
		{
			return;
		}

		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
	// 高度接口
	int _Height(Node *root)
	{
		if (root == NULL)
			return 0;

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}
	// 前序遍历判断
	bool PrevJudge(Node *root, int BNcount, int &certain)
	{
		// 某一条路径结束
		if (root == nullptr)
		{
			if (BNcount != certain)
			{
				cout << "性质4违例: 存在某一路径黑色节点的数量不等!" << endl;
				return false;
			}

			return true;
		}
		// 遇黑--值++
		if (root->_col == BLACK)
		{
			++BNcount;
		}
		// 遇红--连坐判断
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << "性质3违例: 存在连续红节点!" << endl;
			return false;
		}

		return PrevJudge(root->_left, BNcount, certain) && PrevJudge(root->_right, BNcount, certain);
	}
	// 左旋
	void RotateL(Node *dad)
	{
		Node *subR = dad->_right;
		Node *subRL = subR->_left;

		dad->_right = subRL;
		if (subRL)
			subRL->_parent = dad;

		Node *grandpa = dad->_parent;

		subR->_left = dad;
		dad->_parent = subR;

		if (grandpa == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (grandpa->_left == dad)
			{
				grandpa->_left = subR;
			}
			else
			{
				grandpa->_right = subR;
			}

			subR->_parent = grandpa;
		}
	}
	// 右旋
	void RotateR(Node *dad)
	{
		Node *subL = dad->_left;
		Node *subLR = subL->_right;

		dad->_left = subLR;
		if (subLR)
			subLR->_parent = dad;

		Node *grandpa = dad->_parent;

		subL->_right = dad;
		dad->_parent = subL;

		if (dad == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (grandpa->_left == dad)
			{
				grandpa->_left = subL;
			}
			else
			{
				grandpa->_right = subL;
			}
			subL->_parent = grandpa;
		}
	}
};
